/*
 * @lc app=leetcode.cn id=113 lang=golang
 *
 * [113] 路径总和 II
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func pathSum(root *TreeNode, sum int) [][]int {
	res := [][]int{}
	findPath(root, sum, &res, []int{})
	return res
}

func findPath(root *TreeNode, sum int, res *[][]int, stack []int) {
	if root==nil{
		return
	}

	stack = append(stack,root.Val)
	if root.Val==sum && root.Left==nil && root.Right==nil{
		*res = append(*res,append([]int{},stack...))
	}else{
		sum = sum-root.Val
		findPath(root.Left,sum,res,stack)
		findPath(root.Right,sum,res,stack)
	}
}
// @lc code=end

